package week_01;

import java.util.*;

public class Class2 {

    public int numberOfSubarrays_1248(int[] nums, int k) {
        //转 奇偶为1，0
        // 求奇数前缀和
        // s[j]=s[i]-k 有几个
        // count[前缀和值s[j]] 有几个
        int n = nums.length;
        int[] s = new int[n + 1];
        int[] count = new int[n + 1];
        count[s[0]]++;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1] % 2;
            count[s[i]]++;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] - k >= 0) {
                ans += count[s[i] - k];
            }
        }
        return ans;
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        // 差分组
        // 计算每次预定对查分组的影响
        int[] delta = new int[n + 2];
        for (int[] booking : bookings) {
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            delta[first] += seats;
            delta[last + 1] -= seats;
        }
        int[] res = new int[n];
        for (int i = 1; i < delta.length; i++) {
            delta[i] = delta[i - 1] + delta[i];
            res[i-1]=delta[i];
        }

        return res;
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] s = new int[n + 1];
        s[0] = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];
        }

        // 准备以j<i的最小前缀和
        int predix_min = s[0];
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i < s.length; i++) {
            ans = Math.max(ans, s[i] - predix_min);
            predix_min = Math.min(s[i], predix_min);
        }
        return ans;
    }

    public int[] twoSortSum_167(int[] numbers, int target) {
        // 暴力for 循环
        int j = numbers.length - 1;
        for (int i = 0; i < numbers.length; i++) {
            while (i < j && numbers[i] + numbers[j] > target) j--;
            if (i < j && numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
        }
        return new int[]{};
    }

    public List<List<Integer>> threeSum(int[] nums) {
        //先sort，因为不需要返回下标
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        // -nums[i]=nums[j]+nums[k]
        // 遍历找到所有的两数和结果存起来
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            List<List<Integer>> tmpAns = twoSum(nums, i + 1, -nums[i]);
            ans.addAll(tmpAns);
        }
        return ans;
    }

    public List<List<Integer>> twoSum(int[] nums, int start, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int j = nums.length - 1;
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            while (i < j && nums[i] + nums[j] > target) j--;
            if (i < j && nums[i] + nums[j] == target) {
                int i1 = nums[i];
                int i2 = nums[j];
                ans.add(new ArrayList<Integer>() {{
                    add(-target);
                    add(i1);
                    add(i2);
                }});
            }
        }
        return ans;
    }

    public int[] twoSum_1(int[] nums, int target) {
        int n = nums.length;
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            items.add(new Item(nums[i], i));
        }
        Collections.sort(items);
        // 暴力for 循环
        int j = n - 1;
        for (int i = 0; i < n; i++) {

            while (i < j && items.get(i).value + items.get(j).value > target) j--;
            if (i < j && items.get(i).value + items.get(j).value == target) {
                return new int[]{items.get(i).index, items.get(j).index};
            }
        }
        return new int[]{};

    }

    public static class Item implements Comparable {
        private int value;
        private int index;

        public Item(int value, int index) {
            this.value = value;
            this.index = index;
        }


        @Override
        public int compareTo(Object o) {
            Item i2 = (Item) o;
            return this.value - i2.value;
        }
    }

    public int maxArea_11(int[] height) {
        int n = height.length;
        int ans = Integer.MIN_VALUE;
        int i = 0;
        int j = n - 1;
        while (i != j) {
            ans = Math.max(ans, (j - i) * (Math.min(height[i], height[j])));
            if (height[i] >= height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return ans;
    }

    public int maxArea(int[] height) {
        int n=height.length;
        int ans =Integer.MIN_VALUE;
        int j=n-1;
        int i=0;
        while(i<j){
            ans=Math.max(ans,(j-i)*(Math.min(height[i],height[j])));
            if(height[i]==height[j]){
                i++;
                j--;
            }else if(height[i]>=height[j]){
                j--;
            }else{
                i++;
            }
        }
        return ans;
    }


    public int largestRectangleArea(int[] heights) {
        Stack<Rect> stack=new Stack<>();
        int n=heights.length;
        int[] copyArray= Arrays.copyOf(heights,n+1);
        copyArray[n]=0;
        int ans=0;
        for(int i=0;i<copyArray.length;i++){
            int h = copyArray[i];
            int accu_width=0;
            while(!stack.empty()&&stack.peek().height>=h){
                //不满足单调性的元素出栈
                accu_width +=stack.peek().width;
                ans =Math.max(ans,accu_width*stack.peek().height);
                stack.pop();
            }
            // 削平的新元素入栈
            Rect rect=new Rect();
            rect.height=h;
            rect.width=accu_width+1;
            stack.push(rect);
        }
        return ans;
    }

    public class Rect{
        public  int  height;
        public int width;
    }



    public int[] maxSlidingWindow(int[] nums, int k) {
        // 找出滑动窗口 最大值
        //nums = [1,3,-1,-3,5,3,6,7], k = 3
        // 准备单调队列
        Deque<Integer> deque=new LinkedList<>();
        int[] ans =new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            // 过期数据出队列
            while(!deque.isEmpty()&&deque.getFirst()<=i-k) deque.removeFirst();
            // 弹出违背单调性的元素
            while(!deque.isEmpty()&&nums[deque.getLast()]<=nums[i]) deque.removeLast();
            // 末尾添加新元素
            deque.add(i);
            if(i>=k-1) ans[i-k+1] =nums[deque.getFirst()];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 4};
        List<Item> itemArrays = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            itemArrays.add(new Item(nums[i], i));
        }
        Collections.sort(itemArrays);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(itemArrays.get(i).value + ":" + itemArrays.get(i).index);
        }

    }

}
